package com.xy6.struct.queue;

/**
 * 优先队列
 * <p>使用一个有序数据
 * <p>简单、低效
 * <p>插入：O(n)，删除O(1)，查找O(n)
 * 
 * @author zhang
 * @since 2017-09-03
 */
@SuppressWarnings("rawtypes")
public class PriorityQueue<T extends Comparable> {

	private static final int DEFAULT_SIZE = 5;

	private int size = 0;

	Object[] elems;

	public PriorityQueue() {
		elems = new Object[DEFAULT_SIZE];
	}

	@SuppressWarnings("unchecked")
	public void push(T elem) {
		ensureCapacity(elem);
		int i = 0;
		for (i = 0; i < size; i++) {
			T t1 = (T) elems[i];
			if (t1.compareTo(elem) > 0) {
				break;
			}
		}
		for (int j = size; j > i; j--) {
			elems[j] = elems[j - 1];
		}
		elems[i] = elem;
		size++;
	}
	
	@SuppressWarnings("unchecked")
	public T pop(){
		T elem = (T) elems[size - 1];
		size--;
		return elem;
	}

	public int size(){
		return size;
	}
	
	public void print(){
		for(int i=0; i<size; i++){
			System.out.print(elems[i] + " ");
		}
		System.out.println();
	}
	
	private void ensureCapacity(T elem) {
		if (size < elems.length) {
			return;
		}
		// expand array length
		size = size << 1;
		Object[] newelems = new Object[size];
		for (int i = 0; i < elems.length; i++) {
			newelems[i] = elems[i];
		}
		elems = newelems;
	}

}
